﻿#include <stdlib.h>

//插入类排序

/*
* 直接插入类排序：
* 1、从有序子表中找出待插入元素的位置
* 2、给插入位置腾出位置
* 3、待插入元素复制到位置
* 
* 时间复杂度：最好O(n)、最坏/平均O(n²)
* 
*/
void DirectInsert(int R[],int n) {
	int i, j;//j标志要插入的位置
	for (i = 2; i <= n; ++i)
	{
		if (R[i] < R[i - 1]) {
			R[0] = R[i];//R[0]不存元素，复制为哨兵
			for (j = i - 1; R[0] < R[j]; --j) {
				R[j + 1] = R[j];//j向后移
			}
			R[j + 1] = R[0];
		}
	}
}

/*
* 折半插入排序
* 1、折半查找要插入的位置
* 2、插入位置后的元素后移
* 3、复制插入元素
* 
* 时间复杂度：最好O(nlogn)、最坏/平均O(n²)
* 
*/
void MidInsert(int R[], int n) {
	int mid, low, high, j, i;
	for (i = 2; i <= n; ++i)
	{
		R[0] = R[i];//暂存到R[0]
		low = 1;
		high = i - 1;
		//相等后结束循环,查找待插入的位置（即high的后一位）
		while (low <= high) {
			mid = (low + high) / 2;
			if (R[mid] > R[0]) {
				high = mid - 1;
			}
			else {
				low = mid + 1;
			}
		}
		//找到插入位置low=high+1,之后的元素后移
		for (j = i-1; j >= high+1; --j)
		{
			R[j + 1] = R[j];
		}
		R[j + 1] = R[0];
	}
}

/*
* 希尔排序
* 1.对序列按照一定的距离d，划分子序列
* 2.对子序列进行直接插入排序
* 3.不断减小d直到d=1,重复上述过程
* 
*/
void ShellSort(int A[], int n) {
	int j;
	for (int d = n/2; d >=1; d = d/2)//划分距离
	{
		//对子序列的元素直接插入排序
		for (int i = d + 1; i <= n; ++i)//i初始化时指向第一个子表的第二个元素（直接插入排序）
		{
			if (A[i] < A[i - d]) {
				A[0] = A[i];
				//查找插入位置
				for (j = i-d; j >0 && A[0] < A[j]; j-=d)
				{
					A[j + d] = A[j];//后移
				}
				A[j + d] = A[0];
			}
		}
	}
}